package com.my.study.algorithm.leetcode;

/**
 * 编辑距离
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * <p>
 * 你可以对一个单词进行如下三种操作：
 * <p>
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 * @author Carlos
 * @version 1.0.0
 * @date 2023/3/12 10:12
 */
public class EditDistance1 {

    public static void main(String[] args) {
        String s1 = "sun";
        String s2 = "satur";

        int i = minDistance1(s1, s2);

        System.out.println(i);
    }
    
    
    public static int minDistance(String text1, String text2) {
        char[] s = text1.toCharArray();
        char[] t = text2.toCharArray();
        int sLen = s.length;
        int tLen = t.length;
        int[][] f = new int[sLen + 1][tLen + 1];
        for (int j = 1; j <= tLen; j++) {
            f[0][j] = j;
        }
        
        return 0;
    }
    
    
    public static int minDistance1(String text1, String text2) {
        char[] s = text1.toCharArray();
        char[] t = text2.toCharArray();
        int sLen = s.length;
        int tLen = t.length;
        int[][] f = new int[sLen + 1][tLen + 1];
        for (int i = 1; i <= sLen; i++) {
            f[i][0] = i;
        }
        for (int j = 1; j <= tLen ; j++) {
            f[0][j] = j;
        }

        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= tLen; j++) {
                if (s[i-1] == t[j-1]) {
                    f[i][j] = f[i-1][j-1];
                }else {
                    f[i][j] = Math.min(Math.min(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + 1;
                }
                
            }
        }
        
        return f[sLen][tLen];
    }

}
